package cn.itcast.algorithm;

/**
 * 删去k个数字后的最小值
 * 给定整数1593212，删去3个数字，新整数的最小情况是1212
 * 给定整数30200，删去1个数字，新整数的最小情况是200
 * 给定整数10，删去2个数字，新整数的最小情况是0
 * 参考网址：
 * https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653196006&idx=1&sn=50340823d4c2125bc2c361fe45defc3f&chksm=8c99fc3cbbee752a2d42f26817362b02c81d0a422279063309ed3919f55931cba51ad1ae2ba4&scene=0#rd
 * create by zhangtian on 2018/11/23
 */
public class DeleteKMinValue {
    /**
     * 删除整数的k个数字，获得删除后的最小值
     * @param num 原始整数
     * @param k 删除数量
     * @return
     */
    public static String removeDigits(String num, int k){
        // 新整数的最终长度 = 原整数长度 - k
        int newLength = num.length() - k ;
        // 创建一个栈，用于接收所有的数字
        char[] stack = new char[num.length()] ;
        int top = 0 ;

        for (int i = 0; i < num.length(); i++) {
            // 遍历当前数字
            char c = num.charAt(i) ;
            // 当栈顶数字大于遍历到的当前数字，栈顶数字出栈（相当于删除数字）
            while(top > 0 && stack[top - 1] > c && k > 0) {
                top -= 1 ;
                k -= 1 ;
            }
            // 遍历到的当前数字入栈
            stack[top++] = c ;
        }

        // 找到栈中第一个非零数字的位置，以此构建新的整数字符串
        int offset = 0 ;
        while (offset < newLength && stack[offset] == '0') {
            offset ++ ;
        }

        return offset == newLength ? "0" : new String(stack, offset, newLength - offset) ;
    }

    public static void main(String[] args) {
        System.out.println(removeDigits("1593212", 3));
        System.out.println(removeDigits("30200", 1));
        System.out.println(removeDigits("10", 2));
        System.out.println(removeDigits("541270936", 3));
    }
}